Журнал
Научно-технический вестник информационных технологий, механики и оптики
УДК:004.421.2:519.17 004.657
Номер:4 (134)
Скачать PDF0 Кбайт
Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин
Аннотация:
Предмет исследования. Рассмотрена задача поиска путей в графе, которые удовлетворяют заданным контекстно-свободным ограничениям. Задача заключается в поиске всех путей в помеченном ориентированном графе, метки на ребрах которых образуют слова из языка, порожденного входной контекстно-свободной грамматикой. Существует два эффективных подхода к решению поставленной задачи с использованием операций линейной алгебры: с помощью обычного матричного умножения для поиска только одного пути и произведения Кронекера для поиска всех путей в графе. В настоящее время не существует алгоритма, который применяет обычное матричное умножение и способен найти все пути в соответствии с заданным контекстно-свободным ограничением. В работе предложен алгоритм поиска всех путей в графе с заданным контекстно-свободным ограничением, который основан на обычном матричном умножении. Метод. В матрицу смежности входного графа для каждой пары вершин добавляется дополнительная информация о найденных путях между этими вершинами в виде множества возможных промежуточных вершин. На первом этапе осуществлено построение множества матриц, хранящих в себе информацию обо всех путях, удовлетворяющих заданным ограничениям. На втором этапе выполнено построение искомых путей. Основные результаты. Предложенный алгоритм реализован в программе на языке С++. Проведено сравнение с эффективными алгоритмами поиска путей в графе с заданными контекстно-свободными ограничениями. Результаты экспериментального исследования показали, что предложенный алгоритм эффективнее (до 1000 раз быстрее) строит искомые пути, однако в некоторых случаях потребляет до 150 раз больший объем памяти, чем алгоритм, основанный на произведении Кронекера. Практическая значимость. Предложенный алгоритм может быть применен в задачах статического анализа кода, биоинформатике, сетевом анализе, а также в графовых базах данных, когда требуется найти все возможные зависимости в данных, представленных в виде помеченного графа.
Ключевые слова:
Постоянный URL
Статьи в номере
- О возможности применения моностатической схемы построения наземного телескопа при наблюдении космических объектов
- Проблема применения процедуры DREM в задаче идентификации интервально заданных параметров
- Особенности морфологии микро- и нанопористых пленок меди и серебра для фотокаталитического применения, синтезированных с использованием реакции замещения
- Биоинспирированные метаэвристические алгоритмы построения расписаний в облаке: систематический обзор
- Оценка применимости методов асинхронного программирования при решении проблемы согласованности данных в микросервисной среде
- Факторная модель обнаружения и распознавания контура и основных элементов человеческого лица
- Исследование устойчивости информационнотелекоммуникационных сетей в условиях стохастической перколяции узлов
- Система поддержки принятия решений при проведении технологического процесса протонной лучевой терапии
- Определение опасных состояний водителя транспортного средства на основе информации устройств носимой электроники
- Исполняющая машина автоматных программ
- Байесовские функции потерь для моделирования гомоскедастичной алеаторной неопределенности в задаче детекции пыльцы на изображениях
- Алгоритм выявления синтезированного голоса на основе кепстральных коэффициентов и сверточной нейронной сети
- Методика оценки рисков информационных систем на основе анализа поведения пользователей и инцидентов информационной безопасности
- Идентификация аккаунтов пользователей при помощи сравнения изображений: подход на основе pHash
- Исследование движения человека в системах компьютерного зрения на основе скелетной модели
- Решение задач сверх- и гиперзвуковой газовой динамики с использованием модели высокотемпературного воздуха
- Моделирование нарушений безопасности в системах машинного обучения
- Математическое моделирование оптимальной онкотерапии злокачественных опухолей
- Численное исследование разлета смеси газа и частиц с осевой симметрией
- Исследование модулятора двулучепреломления на основе ниобата лития